#include<stdio.h>
#include<malloc.h>

#define MAXIMUM(i,j) ((i>j)?i:j)

typedef struct node Node;

struct node{
	int data;
	Node *left;
	Node *right;
};

int insertTreeNode(int, Node *, int);
Node *CreateNode(int);
int isBalanced(Node *);
int bal(Node *);

int absolute(int d){
	return ((d < 0)?-d:d);
}


int main(){
	Node *root;
	root = CreateNode(22);
	root->left = CreateNode(9);
	root->left->left = CreateNode(4);
	root->left->right = CreateNode(15);
	root->left->right->left = CreateNode(14);
	root->left->right->right = CreateNode(18);
	root->right = CreateNode(27);
	root->right->left = CreateNode(24);
	root->right->right = CreateNode(30);
	root->right->right->left = CreateNode(28);

	printf("\nThe tree is: %s Balanced", isBalanced(root)?"":"Not");
	

	printf("\n--Check Balanced Tree--\n");
	return 0;
}

int insertTreeNode(int data, Node *root, int pos){
	Node *newNode;
	if(newNode = CreateNode(data)){
		if(pos == 1){
			root->right = newNode;
		}else{
			root->left = newNode;
		}
		return 1;
	}else{
		return 0;
	}
}

Node *CreateNode(int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	if(!newNode){
		return NULL;
	}
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}


int isBalanced(Node *root){
	return (bal(root) > -1);
}

int bal(Node *root){
	if(!root){
		return 0;
	}
	int left, right;
	left = bal(root->left);
	if(left == -1){
		return -1;
	}
	right = bal(root->right);
	if(right == -1){
		return -1;
	}
	if(absolute(left-right)>1){
		return -1;
	}
	return (MAXIMUM(left, right) + 1);	
}
